\section{Introduction}
\label{sec:1}
%\vspace{-1mm}
FlexRay is a hybrid communication protocol for automotive networks, i.e., it allows the sharing of the bus between both time-triggered and event-triggered messages. The time-triggered component is the static (ST) segment and the event-triggered component is known as the dynamic (DYN) segment.
The FlexRay bus protocol has garnered widespread support as a vehicular communication network. Its popularity has been driven by the fact that it was developed by a wide 
 consortium~\cite{FR} of automotive companies. In fact, cars equipped with FlexRay are already in the streets or in production~\cite{Fuchs}. As the cost associated with  FlexRay deployment is expected to go down over the next few years, more and more x-by-wire applications are expected to communicate over FlexRay. 

%\vspace{-2mm} 
\subsection {Our contributions and related work}  
 Timing analysis of the DYN segment is NP-hard in the strong sense \cite{PPEPA08} and hence, efficient heuristics \cite{PPEPA08, ZengGN10} have been constructed towards providing upper bounds on the worst-case delays suffered by the messages on DYN segment. However, these methods were limited to the case where slot multiplexing is not permitted on the DYN segment. Zeng et al. have proposed a heuristic \cite{ZengGN10} that outperforms the heuristic proposed by Pop et al. \cite{PPEPA08} with respect to the degree of pessimism. Our experiments show that, in practice, the results obtained by our scheme are significantly better than the method by Zeng et al. \cite{ZengGN10}. Other techniques have limitations like relying on ILP-solvers. They also lack rigorous experimental results because they study only one case study.
 
 %However, none of the above two methods provide any formal guarantees on the approximation ratio. In contrast to these existing techniques, in this paper, we take a theoretical approach and derive an Asymtotic Fully Polynomial Time Approximation Scheme to estimate the worst-case message delays.  Apart from the provable bounds that our method provides, our experiments show that, in practise, the results obtained by our scheme are significantly better than the method by Zeng et al. \cite{ZengGN10}. 
  
  Even more importantly, our analysis is more general than existing methods in the sense  that it can analyze worst-case delays of messages for those FlexRay configurations where slot multiplexing is allowed, i.e., the same priority can be assigned to multiple messages. While timing analysis of the FlexRay dynamic segment has generated significant research interest in recent years, almost all the known approaches~\cite{Andrei07, ZengGN10, PPEPA08, SchmidtS10a} have ignored slot multiplexing. This is inspite of the fact that the FlexRay specification~\cite{FR} allows slot multiplexing. Schneider et. al.~\cite{SchneiderBGC10, Schneider2011} did propose the use of slot multiplexing in the context of FlexRay DYN segment. However, their approach severely restricts the scope of multiplexing because they consider only those messages that are not displaced more than two FlexRay cycles. All other messages are assigned infinite delay. As we illustrate in Section \ref{sec:motivate}, such a method~\cite{SchneiderBGC10, Schneider2011} is very pessimistic and returns negative results even for simple setups where the bandwidth demand from messages is quite small. In contrast, our technique is quite general and can estimate message delays that span over multiple cycles.
 
Finally, our result is significant because it paves the way to design  approaches that optimizes  the delays by configuring parameters that were not in play before. A small example to illustrate this will be discussed in Section \ref{sec:con}. %In this paper, we assume that repetition rates, that are used to define the multiplexed slots of the messages, are given to conduct the timing analysis. Our proposed scheme can be the core engine inside a larger optimization loop, that can configure the repetition rates of messages tune the delays of the messages according to the needs of the application.  We illustrate the impact of repetition rates on message delays with the help of an example in Section \ref{sec:disc}.

%\vspace{-2mm}
\subsection {Overview of the proposed scheme} 
In the case where slot multiplexing is ignored, Pop et al. \cite{PPEPA08} have shown that the core  problem of computing the worst-case delays of messages transmitted on the DYN segment can be transformed into the bin covering problem \cite{LabbeOR1995}. The objective of the bin covering problem is to maximize the number of bins that can be filled to a minimum capacity with a set of items whose weights have been specified. Our algorithm, described in Section~\ref{sec:withoutSM} is directly inspired by recent theoretical advances in approximating the upper bounds on the optimal solution for the bin covering problem that were reported by Jansen and Solis-Oba \cite{JansenTC2003}. %Thus, unlike previously proposed heuristics \cite{PPEPA08,ZengGN10} that provide an upper bound on the worst-case delays of the messages, we can provide formal bounds on the quality of solution returned. Moreover, as our experiments show our approach is significantly less pessimistic than the known approaches \cite{PPEPA08,ZengGN10}. 

However, for the case of slot multiplexing, the problem can not be transformed into the traditional bin covering problem. Rather, the problem becomes what we call as the \textit{bin covering problem with conflicts} in this paper. The approach proposed by Jansen and Solis-Oba was meant for the traditional bin packing problem. Hence, we need to suitably adapt their technique to the problem of bin covering with conflicts when slot multiplexing is allowed in the DYN segment of FlexRay. This will be discussed in detail in Section \ref{sec:withSM}.	

 
%It should be mentioned here that results have been published for schedule synthesis on the ST segment of FlexRay considering slot multiplexing ~\cite{Lukasiewycz2009}. However, the ST segment follows a time-triggered paradigm and these results are not applicable to the DYN segment.
%Instead of a accurate timing analysis framework, the focus of these papers has been on synthesizing schedules or analyzing properties like extensibility or sustainability of existing schedules. 

